package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

import java.util.ArrayList;
import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-13 18:54
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
路径的弱化版定义是：从根节点到某一叶子节点上的所有节点的集合，就是一个路径
高级定义：不非要从 root开始，不非要从leaf结束
 */
public class l_找出路径上value的sum等于num {
    public static void main(String[] args) {
        l_找出路径上value的sum等于num test = new l_找出路径上value的sum等于num();
        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree = new b_MyBinaryTreebyLinked<Integer,Integer>();
        binaryTree.insert(6,6);
        binaryTree.insert(7, 7);
        binaryTree.insert(4,4);
        binaryTree.insert(5, 5);
        binaryTree.insert(8, 8);
        binaryTree.insert(2, 2);
        System.out.println(binaryTree);
        List<List<Integer>> lists = test.checkForward(binaryTree.getRoot(), 9);
        System.out.println(lists.isEmpty());
        for (List<Integer> list : lists) {
            for (Integer element : list) {
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }

    List<List<Integer>> allPathList = new ArrayList<List<Integer>>();

    public List<List<Integer>> checkForward(BSTNode<Integer,Integer> node, Integer key) {
        findAllPath(node);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (List<Integer> path : allPathList) {
            for (int i = 0; i < path.size(); i++) {
                List<Integer> temp = new ArrayList<Integer>();
                int sum = 0;
                for (int j = i; j < path.size(); j++) {
                    sum = sum + path.get(j);
                    temp.add(path.get(j));
                    if (sum == key) {
                        result.add(temp);
                        break;
                    }
                    if (sum > key) {
                        break;
                    }
                }
            }
        }
        return result;
    }

    public void findAllPath(BSTNode<Integer,Integer> node) {
        if (node.left == null && node.right == null) {
            List<Integer> path = new ArrayList<Integer>();
            while (node != null) {
                path.add(node.key);
                node = node.parent;
            }
            allPathList.add(path);
            return;
        }
        if (node.left != null) {
            findAllPath(node.left);
        }
        if (node.right != null) {
            findAllPath(node.right);
        }
    }
}
